Search for: All records

We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for s → t connectivity running in Õ(nm) time, and a deterministic catalytic algorithm for the same running in Õ(n³ m) time. The former algorithm is the first algorithmic use of randomization in CL. The algorithm uses one register per vertex and repeatedly "pushes" values along the edges in the graph. Second, a deterministic catalytic algorithm for simulating random walks which in Õ(m T² / ε) time estimates the probability a T-step random walk ends at a given vertex within ε additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges. Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in n. 

In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows. 1: We unconditionally derandomize catalytic logspace: CBPL = CL. 2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in both CL and P can be solved in polynomial time-bounded CL. 3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL. Our results center around the compress--or--random framework. For the second result, we introduce a simple yet novel compress--or--compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress--or--compress--or--random algorithm that combines runtime compression with a second compress--or--random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction.